perm filename T2[144,DBL] blob
sn#026390 filedate 1973-02-26 generic text, type T, neo UTF8
00100 BLANKS ORIG *+24 ;These locs. should always be blank.
00200 N CON 0 ;The number of nodes
00300 TPL ORIG *+24 ;The desired total path length
00400 LOG CON 0 ;A sequential linear list, whose i th element
00500 * is Floor(log(i)), where log ≡ (log to base 2).
00600 ORIG *+500 ;I have assumed that n will never be > 500.
00700 S CON 0 ;A sequential linear list whose i th element
00800 * is the sum of elements 1 to i of LOG.
00900 ORIG *+500
01000 TREE CON 0 ;An internal representation of the final tree.
01100 ORIG *+500
01200 ZEROS EQU 3500 ;An area which remains as zeros.
01300 VISIT EQU 1:1 ;The field spec. indicating whether or not wehave visited this node yet.
01400 BUFFER ORIG *+800 ;This should be ample to hold a finaltree traversal encoding.
01500 DIFF CON 0 ;Holds the difference between the pure balanced+
01600 * tail tree path length, and the desired TPL.
01700 XOLD CON 0 ;Holds the previous path length, in case we went too far.
01800 K CON 0 ;Holds the number of nodes in the balanced part oftree.
01900 TITLE ALF N
02000 ALF TPL
02100 ALF
02200 ALF
02300 ALF
02400 ALF Doug
02500 ALF Lenat
02600 ALF
02700 ALF CS 14
02800 ALF 4A P
02900 ALF roble
03000 ALF m 4
03100 ALF
03200 ALF Total
03300 ALF Path
03400 ALF Leng
03500 ALF th in
03600 ALF Bina
03700 ALF ry Tr
03800 ALF ees
03900 ORIG *+5
04000 RSON EQU 4:4 ;Field in a TREE node pointing to right son.
04100 LSON EQU 5:5 ;Field specification pointing to the left son.
04200 * note that this restricts n to be under 65; a trivial modification
04300 * will allow n to range up to 500.If n is requested over 2000, a
04400 * total revision of the program would be necessary.
04500 SONS EQU 4:5 ;Field which is blank iff the node is a leaf.
04600 FATHER EQU 3:3 ;Field spec. pointing to the node's parent.
04700 FIELD EQU 4:4 ;Field spec. for the field byte of a MIX instruction.
04800 LPAREN EQU 42
04900 RPAREN EQU 43
05000 STAR EQU 46
05100 READER EQU 16
05200 PRINTER EQU 18
05300 *
05400 *
05500 CONTINU OUT BLANKS(PRINTER)
05600 OUT BLANKS(PRINTER)
05700 START IN N(READER) ;Read n. We are permitted the inefficiency of
05800 JBUS *(READER) ;JBUS instructions. See Knuth and
05900 * my earlier programs for examples
06000 * of more efficient I/O.
06100 LDX N
06200 JXNZ *+2 ;Are we finished the final problem in the run??
06300 HLT ; yes; so we halt.
06400 OUT TITLE(PRINTER) ; Here we
06500 * write out a title line.
06600 OUT N(PRINTER) ;We write n and tpl
06700 JBUS *(PRINTER) ; while they are still in char. form.
06800 ENTA 0
06900 NUM
07000 STA N ; re-store the numeric value of n.
07100 LDX TPL ;Convert TPL from char. code to numeric.
07200 ENTA 0
07300 NUM
07400 STA TPL
07500 ENT1 TREE
07600 LD2 N
07700 ST2 *+1(FIELD)
07800 MOVE ZEROS ;WARNING: INSTRUCTION MODIFICATION HERE.
07900 *
08000 *
08100 * The following loop sets up the first n entries in LOG and in S:
08200 *
08300 ENT1 0 ;rI1 holds the exponent of the current power of 2.
08400 ENT2 0 ;rI2 holds the sum of all previous terms.
08500 ENT3 1 ;rI3 holds 2 to the current power( 2 ↑ <rI1> ).
08600 ENT4 0 ;rI4 stops us when n terms have been computed.
08700 ENTA 1 ;rA tells us when to increase the terms of LOG.
08800 *
08900 JMP LOOP1 ;A standard programming trick, saving n-1 tyme units.
09000 SKIP1 INC3 0,3 ;Double rI3; i.e, increaase its log by 1.
09100 ENTA 0,3 ;rA tells us when to increase the terms of LOG.
09200 INC1 1
09300 LOOP1 INC2 0,1
09400 INC4 1
09500 ST2 S,4
09600 ST1 LOG,4
09700 DECA 1
09800 JAP LOOP1
09900 CMP4 N
10000 JLE SKIP1
10100 *
10200 *
10300 *
10400 *
10500 * This loop is the "guts" of the program: we determine how many nodes
10600 * are in the balanced section, and how many are in the tail.
10700 *
10800 ENT3 0 ;rI3 holds the L*(L+1)/2 term.
10900 LD5 N ;rI5 holds K, the number of nodes in the balanced part.
11000 ENT6 -1 ;rI6 holds L, the number of nodes in the tail.
11100 DEC5 0,6 ;K must always remain equal to N - L.
11200 LOOP2 INC6 1
11300 DEC5 1
11400 INC3 0,6 ;Update this term.
11500 STA XOLD
11600 ENTA 0,6 ;Get the L * Floor(log(k)) term.
11700 MUL LOG,5
11800 SLAX 5
11900 INCA 0,3 ;The accumulator now contains the sum of terms 1,2.
12000 ADD S,5 ;We add in the sum of LOGs from 1 to K: the final term.
12100 CMPA TPL ;See if we have gone far enough....
12200 JL LOOP2 ; we haven't; go back and try again.
12300 * WE HAVE SUCCEEDED !!!
12400 *
12500 LDA TPL
12600 SUB XOLD
12700 STA DIFF
12800 INC5 1
12900 DEC6 1
13100 *
13200 *
13300 *
13400 * Here we set up the tree; only one node will have to be moved.
13500 *
13600 * LOOP3 sets up the balanced section of the tree
13700 *
13800 ENT2 0 ;rI2 now keeps track of the father node.
13900 ST5 K
14000 LOOP3 INC2 1
14100 ENT1 0,2 ;rI1 holds the location of the son(s). In general,
14200 INC1 0,2 ; node m will have as children nodes 2m and 2m+1.
14300 ST1 TREE,2(LSON)
14400 ST2 TREE,1(FATHER)
14500 STZ TREE,1(SONS)
14600 CMP1 K
14700 JGE SETREE2
14800 INC1 1
14900 ST1 TREE,2(RSON)
15000 ST2 TREE,1(FATHER)
15100 STZ TREE,1(SONS)
15200 CMP1 K
15300 JL LOOP3
15400 *
15500 * SETREE2 sets up section 2 of the tree: the tail part
15600 *
15700 SETREE2 ST1 TREE+1,1(FATHER) ;Now rI1 is the father, and rI1+1 is son.
15800 INC1 1
15900 ST1 TREE-1,1(LSON)
16000 CMP1 N
16100 JL SETREE2
16200 *
16300 *
16400 *
16500 * LOOP4 locates a leaf in the balanced section.
16600 *
16700 ENT1 0
16800 LOOP4 INC1 1
16900 LDA TREE,1(SONS)
17000 JANZ LOOP4
17100 *
17200 * Now we have located a leaf. We shall now cut it off the tree:
17300 *
17400 LD2 TREE,1(FATHER)
17500 ENT3 LSON
17600 CMP1 TREE,2(LSON)
17700 JE *+2
17800 ENT3 RSON ;rI3 now contains the field spec. pointing to leaf.
17900 ST3 *+1(FIELD); BE CAREFUL: WE ARE MODIFYING THE NEXT INSTRUCTION!!
18000 STZ TREE,2
18100 *
18200 * Now we see how deep our leaf used to be:
18300 *
18400 ENT3 0
18500 LOOP5 LD2 TREE,2(FATHER)
18600 INC3 1
18700 J2P LOOP5
18800 *
18900 * rI3 now contains that quantity. Now we examine how far we must move it.
19000 *
19100 LDA LOG,5
19200 INCA 1,6 ; rA now contains the depth of the deepest node, node n.
19300 DECA 0,3 ; Subtract the leaf's old depth.
19400 SUB DIFF ; Subtract how many levels down the leaf must be moved.
19500 *
19600 * The accumulator now contains the number of moves upward from the tip of
19700 * the tail of the tree we must make before we insert the leaf back in.
19800 * we move a pointe upward from the final node this number of levels:
19900 *
20000 LD2 N
20100 LOOP6 LD2 TREE,2(FATHER)
20200 DECA 1
20300 JAP LOOP6
20400 *
20500 * Insert the leaf back into the tree at the proper position:
20600 *
20700 ST2 TREE,1(FATHER)
20800 ST1 TREE,2(RSON)
20900 *
21000 * Print out the final tree in post order:
21100 *
21200 ENT1 STAR
21300 ENTA LPAREN
21400 ENTX RPAREN
21500 ENT4 0 ;rI4 holds the present position to be filled in the
21600 * output buffer.
21700 ENT5 1 ;rI5 points to the current position in
21800 * the traversal of the tree.
21900 JMP LOOP7
22000 L7AA DEC4 1
22100 LOOP7A LD5 TREE,5(FATHER)
22200 J5Z LOOP8
22300 STX BUFFER,4
22400 INC4 1
22500 LOOP7 LD3 TREE,5(VISIT) ;If we have visited this node before, move up one
22600 * level, to its father. Else we shall try to go left.
22700 J3P LOOP7A
22800 GOLEFT ENT2 0,5
22900 LD5 TREE,5(LSON)
23000 STA BUFFER,4
23100 INC4 1
23200 LD3 TREE,5(VISIT)
23300 J3P STAY ;If we have visited the left branch already, visit the node itself.
23400 J5P GOLEFT ;If we can continue down the left subtree, do so.
23500 STAY STA TREE,2(VISIT) ;Visit this node. Mark it as such.
23600 ST1 BUFFER-1,4
23700 ENT5 0,2
23800 GORIGHT ENT2 0,5 ;Here we attempt to go right (move to right son).
23900 LD5 TREE,5(RSON)
24000 STA BUFFER,4
24100 INC4 1
24200 J5P LOOP7
24300 LD5 TREE,2(FATHER) ;There is no right son; move upward one level and continue.
24400 STX BUFFER-1,4
24500 *
24600 J5P LOOP7
24700 STZ BUFFER-1,4
24800 *
24900 * Here we do the actual printing of the encoded traversal
25000 *
25100 LOOP8 ENT3 0
25200 LOOP9 OUT BUFFER,3(PRINTER)
25300 INC3 24
25400 DEC4 24
25500 J4NN LOOP9
25600 *
25700 * Go back and read in a new request
25800 *
25900 JMP CONTINU ;This differs from START only in the printing out of 2 blank lines.
26000 *
26100 END START